package Recursion;

import Stack.ArrayStack;

import java.awt.*;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;

/**
 * @author yyq
 * @create 2021-10-12 19:35
 * 1 起始地址mg[1][1] 终点mg[8][8]
 * 2 1 代表墙  2 代表可走通 3 代表走不通  0 代表未走过
 * 3 策略  下-> 左 -> 右 ->上
 */
public class MIgong {

     static int[][] mg = {                           //迷宫地图,1代表墙壁，0代表通路
            {1,1,1,1,1,1,1,1,1,1},
            {1,0,0,1,0,0,0,1,0,1},
            {1,0,0,1,0,0,0,1,0,1},
            {1,0,0,0,0,1,1,0,0,1},
            {1,0,1,1,1,0,0,0,0,1},
            {1,0,0,0,1,0,0,0,0,1},
            {1,0,1,0,0,0,1,0,0,1},
            {1,0,1,1,1,0,1,1,0,1},
            {1,1,0,0,0,0,0,0,0,1},
            {1,1,1,1,1,1,1,1,1,1}
    };

     //map地图 i j 开始位置
     static ArrayStack<Node> findWay(int[][] map,int i,int j){
         ArrayStack<Node> stack= new ArrayStack<Node>(100);
         map[i][j]=2;
         stack.push(new Node(i,j,2));
         while(!stack.isEmpty()){
             //结束条件到达终点
             if(map[1][8]==2) return stack;
             //下
             if(map[i+1][j]==0){
                 map[i+1][j]=2;
                 stack.push(new Node(i+1,j,2));
                 i=i+1;
                 continue;
             }
             //右
             if(map[i][j+1]==0){
                 map[i][j+1]=2;
                 stack.push(new Node(i,j+1,2));
                 j=j+1;
                 continue;
             }

             //上
             if(map[i-1][j]==0){
                 map[i-1][j]=2;
                 stack.push(new Node(i-1,j,2));
                 i=i-1;
                 continue;
             }
             //左
             if(map[i][j-1]==0){
                 map[i][j-1]=2;
                 stack.push(new Node(i,j-1,2));
                 j=j-1;
                 continue;
             }
             //上下左右都不能走时 1 设置该点为3  回溯i j 到前一个点
             map[i][j]=3;
             Node node = stack.pop();
             i=node.x;
             j=node.y;
         }

        return null;
     }

    public static void main(String[] args) {
       // System.out.println(mg.length+" "+mg[0].length);
        for (int i = 0; i < MIgong.mg.length; i++) {
            for (int i1 = 0; i1 < mg[0].length; i1++) {
                System.out.print(mg[i][i1]+" ");
            }
            System.out.println();
        }
        ArrayStack<Node> way = findWay(mg, 1, 1);
        System.out.println("****************");
        for (int i = 0; i < MIgong.mg.length; i++) {
            for (int i1 = 0; i1 < mg[0].length; i1++) {
                System.out.print(mg[i][i1]+" ");
            }
            System.out.println();
        }
        ArrayStack<Node> stack=new ArrayStack<Node>(100);
        while (!way.isEmpty()){
            stack.push(way.pop());
        }
        while(!stack.isEmpty()){
            Node node = stack.pop();
            System.out.println("("+node.x+","+node.y+")");
        }
    }
}

class Node{
    int x;
    int y;
    int statue;
    public Node(int x,int y,int statue){
        this.x=x;
        this.y=y;
        this.statue=statue;
    }
}
